package Search;

import java.util.Arrays;

//斐波那契查找，
//前提，数组是有序的
public class FibonaciSearch {
	public static void main(String[] args) {
		int[] array = {1, 8, 10, 89, 1000, 1234};
		System.out.println(fibSearch(array, 1234));
	}

	public static int maxSize = 20;

	//因为后面需要使用 斐波那契数列，需要先获取一个，
	//非递归的方式得到一个 斐波那契数列
	public static int[] fibo() {
		int[] f = new int[maxSize];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxSize; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}

	//编写 斐波那契查找
	//非递归的方式

	/**
	 * @param array 查找的数组
	 * @param key   需要查找的关键码
	 * @return 返回对应下标
	 */
	public static int fibSearch(int[] array, int key) {
		int low = 0;
		int high = array.length - 1;
		int k = 0;//表示斐波那契分割数值的下标
		int mid = 0;//存放 mid 值
		int f[] = fibo();//获取斐波那契数列
		//获取斐波那契分割数的下标
		while (high > f[k] - 1) {
			//条件成立，没找到 k 的值，继续找
			k++;
		}
		//f[k] 的值可能比数组长度大
		//因此需要使用 Arrays类 构造一个新的数组并指向array
		//不足的部分会使用 0 填充
		int[] temp = Arrays.copyOf(array, f[k]);
		//需要使用 array 数组最后的数 填充 temp
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = array[high];
		}

		//使用 while 来循环处理，找到 key
		while (low <= high) {
			mid = low + f[k - 1] - 1;
			if (key < temp[mid]) {
				//条件成立，因继续向数组左边查找
				high = mid - 1;
				//说明：全部元素 = 前面的元素 + 后面的元素
				//f[k] = f[k-1] + f[k-2]
				//因为前面有 f[k-1] 个元素，所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
				//即在 f[k-1] 前面继续查找 f[k-1 -1]
				k--;
			} else if (key > temp[mid]) {
				//条件成立，向右边查找
				low = mid + 1;
				//说明：以为后面有 f[k-2] 个元素
				//所以可以继续拆分 f[k-1] = f[k-3]+f[k-4];
				//即f[k-1 -2]
				k -= 2;
			} else {
				//找到
				//需要确定返回什么,返回小一点的
				if (mid <= high) {
					return mid;
				} else {
					return high;
				}
			}
		}
		return -1;

	}

}
